/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package tesauro;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.List;

/**
 * Tabla hash que resibe como claves String y almacena obejtos tipo EntradaDiccionario. Resuelve las colisiones mediante
 * la tecnica llamada Chaning. Tambien posee un control de factor de carga que llegado ese valor la tabla se expande y se
 * realiza un rehash de las entradas de la tabla. 
 * 
 * @author Demian, Marcelo.
 */
public class TablaHash implements Serializable{
    private float actualLoadFactor; 
    private float resizeLoadFactor; //cuando el factor de carga llegue o supere este valor se expande la tabla y se hace rehash. Debe ser [0.1, 1.0];
    private int tamanoTabla; //tamaño del array de buckets ... o sea la tabla.
    private int cantidadIndicesOcupados; //indices de la tabla que continen algun bucket.
    private int cantidadElementos; //candidad de elementos que almacena la tabla. no confundir con los bucket que almacena el array tabla.
    private Bucket tabla[]; // array de buckets. un bucke es una lista enlazada que contendra los elementos.
    private int cantidadColisiones; //colisiones al ahcer put. para propositos de debugueo.
    private int cantidadColisonesReHash; //colisiones al hacer reHash. para propositos de debugueo.
    private LlaveDiccionario llave; //instancia que se ultiliza para obtener el hash code de una palabra segun el algoritmo deseado.
    
    public TablaHash(int tamanoInicial, float resizeLoadFactor) {
        this(tamanoInicial);
        
        if(resizeLoadFactor < 0.1 || resizeLoadFactor > 1.0) {
             throw new IllegalArgumentException("parametro resizeLoadFactor debe ser mayor o igual a 0.1 y menor o igual a 1.0.");
        }

        this.resizeLoadFactor = resizeLoadFactor;
    }
    
    public TablaHash(int tamanoInicial) {
        if(tamanoInicial <= 0) {
            throw new IllegalArgumentException("parametro tamanoInicial debe ser mayor a cero. Preferiblemente numero primo.");
        }
        
        tamanoTabla = tamanoInicial;
        tabla = new Bucket[tamanoInicial];
        resizeLoadFactor = 0.75f; //calibrar
        llave = new LlaveDiccionario(new NativeStringHashCode());
    }
    
     /** 
      * Setea la funcion hash a utilizar. Por defecto se usa la funcion nativa
      * de String de Java.
      * Cada vez que se cambie el algoritmo se se hace un re hash sin expandir la tabla.
      * 
      * @param hashCodeStrategy implementacion de algoritmo hash a utilizar.
      */
    public void setHashCodeStrategy(IHashCodeStrategy hashCodeStrategy) {
        llave.setHashCodeStrategy(hashCodeStrategy);
        
        //se llama al reHash con el tamaño actaul solo para que recalcule las entradas con el nuevo algoritmo de hash y no la expanda.
        reHash(tamanoTabla);
    }
    
   /**
    * Obtiene la entrada de la tabla segun la lleva "palabra".
    * 
    * @param palabra palabra a la cual obtener su entrada en el tabla.
    * @return entrada correspondiente o null si la tabla no tiene a "palabra" como llave.
    */
    public EntradaDiccionario get(String palabra) {
        if(palabra == null) {
           throw new IllegalArgumentException("parametro palabra no puede ser nulo.");
        }
        
        llave.setPalabra(palabra.toLowerCase());
        int hashCode = llave.hashCode();
        int idx = Math.abs(hashCode % tamanoTabla);

         for(Bucket bucket = tabla[idx]; bucket != null; bucket = bucket.getNext()){
            if(bucket.getEntrada().getPalabra().equals(llave.getPalabra())){
                return bucket.getEntrada();
            }
         }
        return null;
    }

    /**
     * Agrega a la tabla el par (palabra; sinonimos) donde
     * palabra es la llave y sinonimos la entada.
     *
     * @param palabra
     * @param sinonimos
     */
    public void put(String palabra, List<String> sinonimos) {
        if(palabra == null) {
           throw new IllegalArgumentException("parametro palabra no puede ser nulo.");
        }
        
        if(sinonimos == null) {
           throw new IllegalArgumentException("Sinonimos no puede ser nulo.");
        }

        actualLoadFactor = (float)cantidadIndicesOcupados / tamanoTabla;
        if(actualLoadFactor >= resizeLoadFactor) {
            reHash();
        }
        
        EntradaDiccionario entradaNueva = new EntradaDiccionario(palabra, sinonimos);
        
        llave.setPalabra(palabra.toLowerCase());
        int hashCode = llave.hashCode();
        int idx = Math.abs(hashCode % tamanoTabla);
        
        Bucket bucket = tabla[idx];
        if(bucket == null) {
            bucket = new Bucket();
            bucket.setEntrada(entradaNueva);
            tabla[idx] = bucket;
            cantidadIndicesOcupados++;
        } else {            
            Bucket prevBucket = bucket;
            for(; bucket != null;  prevBucket = bucket, bucket = bucket.getNext()) {
                if(bucket.getEntrada().equals(entradaNueva)) {
                    return;
                }
            }
            
            Bucket nuevo = new Bucket();
            nuevo.setEntrada(entradaNueva);
            prevBucket.setNext(nuevo);
            cantidadColisiones++;
        }
        
        cantidadElementos++;
        return;
    }

    /**
     * Remueve del diccionario una palabra.
     *
     * @param palabra palabra a remover.
     */
    public void remove(String palabra) {
        if(palabra == null) {
           throw new IllegalArgumentException("parametro palabra no puede ser nulo.");
        }
        
        llave.setPalabra(palabra.toLowerCase());
        int hashCode = llave.hashCode();
        int idx = Math.abs(hashCode % tamanoTabla);

        for(Bucket bucket = tabla[idx], prevBucket = bucket; bucket != null;  prevBucket = bucket, bucket = bucket.getNext()) {
            EntradaDiccionario entrada = bucket.getEntrada();
            if(entrada.getPalabra().equals(llave.getPalabra())) {
                Bucket next = bucket.getNext();
                prevBucket.setNext(next);
                bucket.setNext(null);
                
                if(bucket == tabla[idx]) {
                    tabla[idx] = next;
                }
                
                //si no hay mas nada en el indice de la tabla.
                if(tabla[idx] == null) {
                    cantidadIndicesOcupados--;
                    actualLoadFactor =(float) cantidadIndicesOcupados / tamanoTabla;
                }
                
                cantidadElementos--;                
                break;
            }
        }
    }

    public void removeAll() {
        for(int i = 0; i < tamanoTabla; i++) {
            tabla[i] = null;
        }
        
        actualLoadFactor = 0.0f;
        cantidadIndicesOcupados = 0;
        cantidadElementos = 0;
        cantidadColisiones = 0;
        cantidadColisonesReHash = 0;        
        return;
    }

    public int size() {
        return cantidadElementos;
    }
    
    public float getActualLoadFactor() {
        return actualLoadFactor;
    }
    
    public int getCantidadColisiones() {
        return this.cantidadColisiones;
    }
    
    public int getCantidadColisonesHash() {
        return this.cantidadColisonesReHash;
    }
    
    public void reHash() {
        reHash( tamanoTabla * 2);
    }

    boolean contains(String texto) {
        llave.setPalabra(texto.toLowerCase());
        int hashCode = llave.hashCode();
        int idx = Math.abs(hashCode % tamanoTabla);
        Bucket bucket =  tabla[idx];
        boolean result = false;
        
        while(bucket != null) {
            EntradaDiccionario entrada = bucket.getEntrada();
            if(entrada.getPalabra().equals(texto)) {
                result = true;
                break;
            }
            bucket = bucket.getNext();
        }
        
        return result;
    }
    
    /**
     * Obtiene todas las claves de la tabla hash 
     * 
     * @param 
     * 
     */
    public List<String> obtenerLlave(){
        List<String> listKeys = new ArrayList<String>(); 
        
    	for (int i = 0; i < tabla.length; i++) {
			if(tabla[i] != null){
				listKeys.add(tabla[i].getEntrada().getPalabra());
			}
		}    	
    	return listKeys;
    }

    public IHashCodeStrategy getHashCodeStrategy() {
        return this.llave.getHashCodeStrategy();
    }
    
    /**
     * Expande la tabla al nuevo tamaño y recalcula todas las entradas.
     *  Si el tamano nuevo es menor al actual ninguna accion se lleva a cabo.
     * Si el tamano es el mismo que el actual no se expande la tabla pero se
     * recalculan todas las entradas de nuevo.
     * 
     * @param nuevoTamano nuevo tamano que tendra el array de buckets.
     */
    private void reHash(int nuevoTamano) {
        if(nuevoTamano < tamanoTabla) {
            return;
        }
        
        cantidadColisiones = 0;
        cantidadColisonesReHash = 0;
        actualLoadFactor = 0.0f;
        cantidadElementos = 0;
        cantidadIndicesOcupados = 0;        
        tamanoTabla = nuevoTamano;
        Bucket []nuevaTabla = new Bucket[tamanoTabla];            
        
        for(int i = 0; i < tabla.length; i++) {
           Bucket oldBucket = tabla[i];
            for(; oldBucket != null; oldBucket = oldBucket.getNext()) {
                EntradaDiccionario entrada = oldBucket.getEntrada();
                llave.setPalabra(entrada.getPalabra());
                int hashCode = llave.hashCode();
                int idx = Math.abs(hashCode % tamanoTabla);
                
                Bucket bucket = nuevaTabla[idx];
                if(bucket == null) {
                    bucket = new Bucket();
                    bucket.setEntrada(entrada);
                    nuevaTabla[idx ] = bucket;
                    cantidadIndicesOcupados++;
                    actualLoadFactor =(float)cantidadIndicesOcupados / tamanoTabla;
                } else {
                    while(bucket.getNext() != null) {
                        bucket = bucket.getNext();
                    }
                    
                    Bucket nuevoBucket = new Bucket();
                    nuevoBucket.setEntrada(entrada);
                    bucket.setNext(nuevoBucket);
                     cantidadColisonesReHash++;
                }
                
                cantidadElementos++;
            }
        }
        
        tabla = nuevaTabla;
        cantidadColisiones = cantidadColisonesReHash;
        return;
    }
        
    public String toString() {
        StringBuffer buffer = new StringBuffer();
        
        buffer.append("["+  this.cantidadIndicesOcupados + ", " + this.tamanoTabla + ", " + this.actualLoadFactor + ", " +  this.resizeLoadFactor + ", " + this.cantidadElementos);
        for(int i = 0; i < this.tamanoTabla; i++) {
            if(tabla[i] == null) {
                continue;
            }
            
            buffer.append(", " + tabla[i]);
        }
        buffer.append("]");
        return buffer.toString();
    }

    /**
     * Imprime info de debug para temas de colisiones y tiempos.
     */
   public  String printDebugInfo() {
        StringBuffer buffer = new StringBuffer();
        
        buffer.append("Factor carga actual: " + this.actualLoadFactor);
        buffer.append("\nColisiones actuales: " + this.cantidadColisiones);
        buffer.append("\nColisiones durante reHash: " + this.cantidadColisonesReHash);
        
        return buffer.toString();
    }

	public Bucket[] getTabla() {
		return tabla;
	}

	public void setTabla(Bucket[] tabla) {
		this.tabla = tabla;
	}
}